package com.xuyuan.arithmetic.datastructure.quest;


import org.junit.jupiter.api.Test;

import java.util.ArrayList;
import java.util.Collections;
import java.util.List;
import java.util.Random;
import java.util.stream.Collectors;
import java.util.stream.IntStream;

/**
 * 排序算法
 *
 * @author xuyuan
 */
public class SortSolution {

    @Test
    public void test() {
        int[] a = {1, 9, 8, 5, 4, 6, 7, 2, 3, 10};
        mergeSort(a);
        System.out.println(IntStream.of(a).boxed().map(String::valueOf).collect(Collectors.joining(",")));
    }

    /**
     * 冒泡排序：将数组相邻元素两两比较，右侧保存大值，左侧保存小值。这样操作后数组最右端的元素即为该数组中所有元素的最大值。接着对该数组除最右端的n-1个元素进行同样的操作，再接着对剩下的n-2个元素做同样的操作，直到整个数组有序排列。
     * 时间复杂度：O(n²)，空间复杂度为O(1)。
     */
    void bubbleSort(int[] a) {
        for (int i = 0; i < a.length - 1; i++) {
            for (int j = 0; j < a.length - 1 - i; j++) {
                if (a[j] > a[j + 1]) {
                    int temp = a[j];
                    a[j] = a[j + 1];
                    a[j + 1] = temp;
                }
            }
        }
    }

    /**
     * 添加边界条件：在冒泡排序中，当数组无序时，会继续进行排序，但是当数组有序时，会退出循环。
     */
    void bubbleSortWithBord(int[] a) {
        for (int i = 0; i < a.length - 1; i++) {
            boolean flag = false;
            for (int j = 0; j < a.length - 1 - i; j++) {
                if (a[j] > a[j + 1]) {
                    int temp = a[j];
                    a[j] = a[j + 1];
                    a[j + 1] = temp;
                    flag = true;
                }
            }
            if (!flag) {
                break;
            }
        }
    }

    /**
     * 选择排序:找到数组中最小的元素放到数组最左侧，接着在剩下的n-1个数字中找到最小值min2，如果最小值min2不等于arr[1]，则交换这两个数字，依次类推，直到数组arr有序排列。算法的时间复杂度为O(n^2)。
     * 时间复杂度：O(n²)，空间复杂度为O(1)。
     */
    void selectSort(int[] a) {
        for (int i = 0; i < a.length - 1; i++) {
            int minIndex = i;
            for (int j = i + 1; j < a.length; j++) {
                if (a[j] < a[minIndex]) {
                    minIndex = j;
                }
            }
            if (minIndex != i) {
                int temp = a[i];
                a[i] = a[minIndex];
                a[minIndex] = temp;
            }
        }
    }

    /**
     * 插入排序:通过构建有序序列，对于未排序数据，在已排序序列中从后向前扫描，找到相应位置并插入。
     * 时间复杂度：O(n²)，空间复杂度：O(1)。
     */
    void insertSort(int[] a) {
        for (int i = 1; i < a.length; i++) {
            int temp = a[i];
            int j = i - 1;
            while (j >= 0 && a[j] > temp) {
                a[j + 1] = a[j];
                j--;
            }
            a[j + 1] = temp;
        }
    }

    /**
     * 希尔排序：先选定一个小于N的整数gap作为第一增量，然后将所有距离为gap的元素分在同一组，并对每一组的元素进行直接插入排序。然后再取一个比第一增量小的整数作为第二增量，重复上述操作…当增量的大小减到1时，就相当于整个序列被分到一组，进行一次直接插入排序，排序完成。
     * 步长+分组 - 由于前面循环，数据局部有序之后，最后一次插入排序的很快，效率相对于插入排序会提高。(优化版的插入排序)
     * 时间复杂度：O(nlog n) 和 O(n²) 之间，空间复杂度：O(1)。
     */
    void shellSort(int[] a) {
        for (int gap = a.length / 2; gap >= 1; gap /= 2) {
            for (int i = gap; i < a.length; i++) {
                int temp = a[i];
                int j = i - gap;
                while (j >= 0 && a[j] > temp) {
                    a[j + gap] = a[j];
                    j -= gap;
                }
                a[j + gap] = temp;
            }
        }
    }


    /**
     * 归并排序：将待排序数组分割成若干个子数组，每个子数组都是有序的，然后依次合并子数组，得到完全有序的数组。
     * 时间复杂度：O(nlog n)，空间复杂度为O(n)。
     */
    void mergeSort(int[] a) {
        if (a == null || a.length <= 1) {
            return;
        }
        int[] tempArray = new int[a.length];
        mergeSortHelper(a, tempArray, 0, a.length - 1);
    }

    /**
     * @param a
     * @param tempArray 临时数组,用于临时存放有序元素
     * @param left      左边数组起始索引
     * @param right     右边数组结束索引
     */
    void mergeSortHelper(int[] a, int[] tempArray, int left, int right) {
        if (left >= right) {
            return; // 子数组长度为1或0，已经有序
        }

        int mid = left + (right - left) / 2;
        mergeSortHelper(a, tempArray, left, mid); // 排序左半部分
        mergeSortHelper(a, tempArray, mid + 1, right); // 排序右半部分
        merge(a, tempArray, left, mid, right); // 合并两个有序子数组
    }

    /**
     * @param a
     * @param tempArray 临时数组,用于临时存放有序元素
     * @param left      左边数组起始索引
     * @param mid       中间索引
     * @param right     右边数组结束索引
     */
    void merge(int[] a, int[] tempArray, int left, int mid, int right) {
        int i = left; // 左半部分的起始索引
        int j = mid + 1; // 右半部分的起始索引
        int k = left; // 临时数组的起始索引

        // 将左右两部分的数据按顺序放入临时数组
        while (i <= mid && j <= right) {
            if (a[i] <= a[j]) {
                tempArray[k++] = a[i++];
            } else {
                tempArray[k++] = a[j++];
            }
        }

        // 将剩余的左半部分数据复制到临时数组
        while (i <= mid) {
            tempArray[k++] = a[i++];
        }

        // 将剩余的右半部分数据复制到临时数组
        while (j <= right) {
            tempArray[k++] = a[j++];
        }

        // 将临时数组中的数据复制回原数组
        System.arraycopy(tempArray, left, a, left, right - left + 1);
    }

    private static final Random RANDOM = new Random();

    /**
     * 快速排序：通过一趟排序将待排序记录分割成独立的两部分，其中一部分的所有数据都比另一部分的所有数据要小，然后再按此方法对这两部分数据分别进行快速排序，整个排序过程可以递归进行，以此达到整个数据变成有序序列。
     * 时间复杂度：O(nlog n) 和 O(n²) 之间，空间复杂度为O(log n)。
     */
    void quickSort(int[] a) {
        if (a == null || a.length <= 1) {
            return;
        }
        quickSortRecursive(a, 0, a.length - 1);
    }

    /**
     * 快速排序递归实现
     *
     * @param a    待排序的数组
     * @param low  起始索引
     * @param high 结束索引
     */
    void quickSortRecursive(int[] a, int low, int high) {
        if (low >= high) {
            return;
        }
        int pivotIndex = partition(a, low, high);
        quickSortRecursive(a, low, pivotIndex - 1);
        quickSortRecursive(a, pivotIndex + 1, high);
    }

    /**
     * 分区函数
     *
     * @param a    待排序的数组
     * @param low  起始索引
     * @param high 结束索引
     * @return 枢纽位置
     */
    private int partition(int[] a, int low, int high) {
        // 随机选择一个枢轴，并将其与最后一个元素交换
        int randomPivotIndex = low + RANDOM.nextInt(high - low + 1);
        swap(a, high, randomPivotIndex);

        int pivot = a[high];
        int i = low - 1;
        for (int j = low; j < high; j++) {
            if (a[j] <= pivot) {
                i++;
                swap(a, i, j);
            }
        }
        swap(a, i + 1, high);
        return i + 1;
    }

    /**
     * 交换数组中的两个元素
     *
     * @param a 数组
     * @param i 索引1
     * @param j 索引2
     */
    void swap(int[] a, int i, int j) {
        if (i == j) {
            return;
        }
        int temp = a[i];
        a[i] = a[j];
        a[j] = temp;
    }

    /**
     * 堆排序：通过构建堆，将堆顶元素与堆中最后一个元素交换，然后对堆中剩余的元素重新构建堆，直到堆中元素为1，则排序完成。
     * 时间复杂度：O(nlog n)，空间复杂度：O(n)。
     */
    void heapSort(int[] a) {
        if (a == null || a.length <= 1) {
            return;
        }
        int n = a.length;
        // 构建最大堆
        for (int i = n / 2 - 1; i >= 0; i--) {
            heapify(a, n, i);
        }
        // 一个个从堆顶取出元素
        for (int i = n - 1; i > 0; i--) {
            // 将当前堆顶元素（最大值）与堆的最后一个元素交换
            swap(a, 0, i);
            // 调整堆，使其重新成为最大堆
            heapify(a, i, 0);
        }
    }

    /**
     * 调整堆，使其满足最大堆的性质
     *
     * @param a 数组
     * @param n 堆的大小
     * @param i 当前节点的索引
     */
    void heapify(int[] a, int n, int i) {
        int largest = i; // 初始化最大值为当前节点
        int left = 2 * i + 1; // 左子节点
        int right = 2 * i + 2; // 右子节点

        // 如果左子节点存在且大于当前节点
        if (left < n && a[left] > a[largest]) {
            largest = left;
        }

        // 如果右子节点存在且大于当前节点
        if (right < n && a[right] > a[largest]) {
            largest = right;
        }

        // 如果最大值不是当前节点
        if (largest != i) {
            swap(a, i, largest);

            // 递归调整受影响的子树
            heapify(a, n, largest);
        }
    }


    /**
     * 桶排序：将待排序元素放入到若干个桶中，每个桶是一个有序的数组，然后对每个桶进行排序，最后将所有桶中的元素合并成一个有序的数组。
     * 时间复杂度：O(n+k)，空间复杂度：O(n+k)。
     */
    void bucketSort(int[] a) {
        if (a == null || a.length <= 1) {
            return;
        }

        int n = a.length;
        int max = a[0];
        int min = a[0];

        // 找到数组中的最大值和最小值
        for (int num : a) {
            if (num > max) {
                max = num;
            }
            if (num < min) {
                min = num;
            }
        }

        // 计算桶的数量
        int bucketCount = (max - min) / n + 1;
        List<List<Integer>> buckets = new ArrayList<>(bucketCount);

        // 初始化桶
        for (int i = 0; i < bucketCount; i++) {
            buckets.add(new ArrayList<>());
        }

        // 将元素分配到桶中
        for (int num : a) {
            int index = (num - min) / n;
            buckets.get(index).add(num);
        }

        // 对每个桶进行排序，并合并到结果数组中
        int index = 0;
        for (List<Integer> bucket : buckets) {
            if (!bucket.isEmpty()) {
                // 使用插入排序对每个桶进行排序
                Collections.sort(bucket);
                for (int num : bucket) {
                    a[index++] = num;
                }
            }
        }
    }


    /**
     * 计数排序：通过统计待排序数组中每个元素的出现次数，然后根据出现次数将元素依次放入有序数组中。
     * 时间复杂度：O(n+k)，空间复杂度：O(n+k)。
     */
    void countSort(int[] a) {
        if (a == null || a.length <= 1) {
            return;
        }

        int n = a.length;
        int max = a[0];
        int min = a[0];

        // 找到数组中的最大值和最小值
        for (int num : a) {
            if (num > max) {
                max = num;
            }
            if (num < min) {
                min = num;
            }
        }

        // 计数数组的大小
        int range = max - min + 1;
        int[] count = new int[range];

        // 统计每个元素出现的次数
        for (int num : a) {
            count[num - min]++;
        }

        // 计算每个元素在排序后数组中的位置
        for (int i = 1; i < range; i++) {
            count[i] += count[i - 1];
        }

        // 创建临时数组存储排序后的结果
        int[] temp = new int[n];

        // 根据计数数组将元素放置到正确的位置
        for (int i = n - 1; i >= 0; i--) {
            int num = a[i];
            temp[count[num - min] - 1] = num;
            count[num - min]--;
        }

        // 将临时数组中的元素复制回原数组
        System.arraycopy(temp, 0, a, 0, n);
    }


    /**
     * 基数排序：通过将待排序数组中的元素按照低位优先的方式，从低位到高位依次进行排序，得到有序数组。
     * 时间复杂度：O(nk)，空间复杂度：O(n+k)。
     */
    void radixSort(int[] a) {
        if (a == null || a.length <= 1) {
            return;
        }

        int n = a.length;
        int max = a[0];

        // 找到数组中的最大值
        for (int num : a) {
            if (num > max) {
                max = num;
            }
        }

        // 从最低位到最高位逐位排序
        for (int exp = 1; max / exp > 0; exp *= 10) {
            countingSortByDigit(a, exp);
        }
    }

    /**
     * 根据指定的位数进行计数排序
     *
     * @param a   数组
     * @param exp 位数（1, 10, 100, ...）
     */
    void countingSortByDigit(int[] a, int exp) {
        int n = a.length;
        int[] output = new int[n];
        int[] count = new int[10];

        // 统计每个位数出现的次数
        for (int i = 0; i < n; i++) {
            int digit = (a[i] / exp) % 10;
            count[digit]++;
        }

        // 计算每个位数在排序后数组中的位置
        for (int i = 1; i < 10; i++) {
            count[i] += count[i - 1];
        }

        // 根据计数数组将元素放置到正确的位置
        for (int i = n - 1; i >= 0; i--) {
            int digit = (a[i] / exp) % 10;
            output[count[digit] - 1] = a[i];
            count[digit]--;
        }

        // 将临时数组中的元素复制回原数组
        System.arraycopy(output, 0, a, 0, n);
    }
}
